<!doctype html>
<html>
<head>
	<title>Sort Algorithm</title>
	<script src="jquery-1.12.3.min.js"></script>
</head>
<style>
	input{
        width:50px;
        height:50px;
    }
    input:hover{
		background-color: greenyellow;
	}
</style>
<body style="margin:0;padding:0;">
    <button id="quickSort">quickSort</button>
    <button id="bubbleSort">bubbleSort</button>
    <button id="selectionSort">selectionSort</button>
    <button id="insertionSort">insertionSort</button>
    <button id="shellSort">shellSort</button>
    <button id="mergeSort">mergeSort</button>
    <button id="heapSort">heapSort</button>
    <button id="countingSort">countingSort</button>
    <button id="bucketSort">bucketSort</button>
    <button id="radixSort">radixSort</button>
    <button id="reset">reset</button>
    <table border="1" cellspacing="0" cellpadding="0" align="center" valign="center" style="margin-top:10%;" id="base">
        <tr>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
            <td><input /></td>
        </tr>
    </table>
    
	<script>
        $(function(){
            reset();

            $('#quickSort').on("click",function(){
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                quickSort(arr,0,arr.length-1);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#bubbleSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                bubbleSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#selectionSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                selectionSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#insertionSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                insertionSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#shellSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                shellSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#mergeSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                let arr2 = mergeSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr2[i]);
                }
            });

            $('#heapSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                heapSort(arr);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#countingSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                countingSort(arr,100);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#bucketSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                bucketSort(arr,1000);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#radixSort').on("click", function () {
                let arr = new Array();
                for (let i = 0; i < $("#base input").length; i++) {
                    arr.push(parseInt($("#base input").eq(i).val()));
                }
                radixSort(arr,5);
                for (let i = 0; i < arr.length; i++) {
                    $("#base input").eq(i).val(arr[i]);
                }
            });

            $('#reset').on("click", function () {
                reset();
            });
        });
        let reset = () => {
            for (let i = 0; i < $("#base input").length; i++) {
                $("#base input").eq(i).val(parseInt(Math.random() * 100));
            }
        }
        /////////////////////////////////////////////快速排序
        let quickSort = (arr, l, r) => {//对从arr[l]到arr[r]的元素进行排序
            let temp, i = l, j = r;
            if (i < j) {
                temp = arr[i];
                while (i != j) {
                    while (i < j && arr[j] > temp) {//从右往左扫描到一个小于temp的元素
                        j--;
                    }
                    if (i < j) {
                        arr[i] = arr[j];//把j的元素放在i的位置上（temp的左边）
                        i++;//i右移一位
                    }
                    while (i < j && arr[i] < temp) {//从左往右扫描找到一个大于temp的元素
                        i++;
                    }
                    if (i < j) {
                        arr[j] = arr[i];//把i的元素放在j的位置上(temp的右边)
                        j--;
                    }
                }
                arr[i] = temp;//将temp放在最终位置
                quickSort(arr, l, i - 1);//递归地对temp左边的元素进行排序
                quickSort(arr, i + 1, r);//递归地对temp右边的元素进行排序
            }
        }
        /////////////////////////////////////////////冒泡排序
        let bubbleSort = (arr) => {
            let len = arr.length;
            for (let i = 0; i < len; i++) {
                for (let j = 0; j < len - 1 - i; j++) {
                    if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                        let temp = arr[j+1];        //元素交换
                        arr[j+1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            return arr;
        }
        /////////////////////////////////////////////选择排序
        let selectionSort = (arr) => {
            let len = arr.length;
            let minIndex, temp;
            for (let i = 0; i < len - 1; i++) {
                minIndex = i;
                for (let j = i + 1; j < len; j++) {
                    if (arr[j] < arr[minIndex]) {     //寻找最小的数
                        minIndex = j;                 //将最小数的索引保存
                    }
                }
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            return arr;
        }
        /////////////////////////////////////////////插入排序
        //有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序
        let insertionSort = (arr) => {
            let len = arr.length;
            let preIndex, current;
            for (let i = 1; i < len; i++) {
                preIndex = i - 1;
                current = arr[i];
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + 1] = arr[preIndex];
                    preIndex--;
                }
                arr[preIndex + 1] = current;
            }
            return arr;
        }
        /////////////////////////////////////////////希尔排序
        //分组插入排序
        shellSort = (arr) => {  
            let gap =Math.floor(arr.length/2);  
            while(gap>=1){  
                for(let i =gap;i<arr.length;i++){  
                    let j,temp=arr[i];  
                    for(j=i-gap;j>=0&&temp<arr[j];j=j-gap){  
                        arr[j+gap]=arr[j];  
                    }  
                    arr[j+gap]=temp;  
                }  
                gap=Math.floor(gap/2);  
            }  
        }  
        /////////////////////////////////////////////归并排序
        let mergeSort = (arr) => {//采用自上而下的递归方法
            // 设置终止的条件，
            if (arr.length < 2) {
                return arr;
            }
            //设立中间值
            let middle = parseInt(arr.length / 2);
            //第1个和middle个之间为左子列
            let left = arr.slice(0, middle);
            //第middle+1到最后为右子列
            let right = arr.slice(middle);
            if (left == "undefined" && right == "undefined") {
                return false;
            }
            return merge(mergeSort(left), mergeSort(right));
        }

        let merge = (left, right) => {
            let result = [];

            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    //把left的左子树推出一个，然后push进result数组里
                    result.push(left.shift());
                } else {
                    //把right的右子树推出一个，然后push进result数组里
                    result.push(right.shift());
                }
            }
            //经过上面一次循环，只能左子列或右子列一个不为空，或者都为空
            while (left.length) {
                result.push(left.shift());
            }
            while (right.length) {
                result.push(right.shift());
            }
            return result;
        }
        /////////////////////////////////////////////堆排序
        //堆实际上是一个完全二叉树，并且其左右子节点都不大于父节点（父节点大于子节点）
        let len;    //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

        let buildMaxHeap = (arr) => {   //建立大顶堆
            len = arr.length;
            for (let i = Math.floor(len / 2 - 1); i >= 0; i--) {
                heapify(arr, i);
            }
        }

        let heapify = (arr, i) => {     //堆调整
            let left = 2 * i + 1,//左节点
                right = 2 * i + 2,//右节点
                largest = i;//父节点

            if (left < len && arr[left] > arr[largest]) {
                largest = left;
            }

            if (right < len && arr[right] > arr[largest]) {
                largest = right;
            }

            if (largest != i) {
                swap(arr, i, largest);
                heapify(arr, largest);//其子节点变父节点，再次调整
            }
        }

        let swap = (arr, i, j) => {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        let heapSort = (arr) => {
            //初始化，i从最後一个父节点开始调整
            buildMaxHeap(arr);
            //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
            for (let i = arr.length - 1; i > 0; i--) {
                swap(arr, 0, i);
                len--;
                heapify(arr, 0);//从根节点开始递归
            }
            return arr;
        }
        /////////////////////////////////////////////计数排序
        //把数放入数组下标对应位置，并计数，遍历数组输出数
        let countingSort = (arr, maxValue) => {
            let bucket = new Array(maxValue + 1),
                sortedIndex = 0,
                arrLen = arr.length,
                bucketLen = maxValue + 1;

            for (let i = 0; i < arrLen; i++) {
                if (!bucket[arr[i]]) {
                    bucket[arr[i]] = 0;
                }
                bucket[arr[i]]++;
            }

            for (let j = 0; j < bucketLen; j++) {
                while (bucket[j] > 0) {
                    arr[sortedIndex++] = j;
                    bucket[j]--;
                }
            }

            return arr;
        }
        /////////////////////////////////////////////桶排序
        let bucketSort = (arr, bucketSize) => {
            if (arr.length === 0) {
                return arr;
            }

            let i;
            let minValue = arr[0];
            let maxValue = arr[0];
            for (i = 1; i < arr.length; i++) {
                if (arr[i] < minValue) {
                    minValue = arr[i];                //输入数据的最小值
                } else if (arr[i] > maxValue) {
                    maxValue = arr[i];                //输入数据的最大值
                }
            }

            //桶的初始化
            let DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
            bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
            let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
            let buckets = new Array(bucketCount);
            for (i = 0; i < buckets.length; i++) {
                buckets[i] = [];
            }

            //利用映射函数将数据分配到各个桶中
            for (i = 0; i < arr.length; i++) {
                buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
            }

            arr.length = 0;
            for (i = 0; i < buckets.length; i++) {
                insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序
                for (let j = 0; j < buckets[i].length; j++) {
                    arr.push(buckets[i][j]);
                }
            }

            return arr;
        }
        /////////////////////////////////////////////基数排序
        // 基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：
        // 278、109、063、930、589、184、505、269、008、083
        // 我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8 ，k2(十位) = 7 ，k3 = (百位) = 2。
        // 然后从最低位个位开始(从最次关键字开始) ，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0 - 9的，因此桶大小为10) ，再依次输出桶中的数据得到下面的序列。
        // 930、063、083、184、505、278、008、109、589、269
        // 再对上面的序列接着进行针对k2的桶分配，输出序列为：
        // 505、008、109、930、063、269、278、083、184、589
        // 最后针对k3的桶分配，输出序列为：
        // 008、063、083、109、184、269、278、505、589、930
        //LSD Radix Sort
        let counter = [];
        let radixSort = (arr, maxDigit) => {
            let mod = 10;
            let dev = 1;
            for (let i = 0; i < maxDigit; i++ , dev *= 10, mod *= 10) {
                for (let j = 0; j < arr.length; j++) {
                    let bucket = parseInt((arr[j] % mod) / dev);
                    if (counter[bucket] == null) {
                        counter[bucket] = [];
                    }
                    counter[bucket].push(arr[j]);
                }
                let pos = 0;
                for (let j = 0; j < counter.length; j++) {
                    let value = null;
                    if (counter[j] != null) {
                        while ((value = counter[j].shift()) != null) {
                            arr[pos++] = value;
                        }
                    }
                }
            }
            return arr;
        }
    </script>
</body>
</html>
